//https://leetcode.cn/problems/course-schedule-iv/description/?envType=daily-question&envId=2023-09-12


class Solution {
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        bool graph[numCourses][numCourses];
        memset(graph, 0, sizeof(bool)*numCourses*numCourses);

        // 构建图
        for (vector<int>& p : prerequisites)
        {
            graph[p[0]][p[1]] = true;
            // cout << p[0] << " " << p[1] << endl;
        }
        for (int k = 0; k < numCourses; ++k)
        {
            for (int i = 0; i < numCourses; ++i)
            {
                for (int j = 0; j < numCourses; ++j)
                {
                    if (graph[i][k] && graph[k][j])
                    {
                        graph[i][j] = true; 
                    }
                    // graph[i][j] |= graph[i][k] && graph[k][j];
                }
            }
        }

        // 遍历quries直接从graph得到结果
        int n = queries.size();
        vector<bool> res(n);
        for (int i = 0; i < n; ++i)
        {
            // cout << "res " << i << " : " << graph[queries[i][0]][queries[i][1]] << endl;
            res[i] = graph[queries[i][0]][queries[i][1]];
        }
        return res;
    }
};

